#include "Parser.h"
#include <cmath>
#include <iostream>

using namespace std;

//=================================================================
// Parser
//=================================================================

void Parser::init()
{
	vector<Parser::hNode> v;
	int i = 0;
	int n = m_expression.size();
	Parser::hNode node;
	bool prev_is_number = false;
	while(i<n)
	{
		node = get_next(i,m_expression, prev_is_number);
		if(node)
		{
			v.push_back(node);
			Parser::Number*   num = dynamic_cast<Parser::Number*>(node);
			Parser::Variable* var = dynamic_cast<Parser::Variable*>(node);
			if(num || var)
				prev_is_number = true;
			else 
				prev_is_number = false;
			if(var) m_variables.push_back(var);
		}
	}

	#ifdef _DEBUG
	for(unsigned k=0 ; k<v.size() ; ++k)
	cout << (*(v[k])) <<' ';
	cout << endl;
	#endif

	tree(v,0,v.size()-1,m_root);

	int max_index = -1, index;
	n = m_variables.size();
	for(i=0 ; i<n ; ++i)
	{
		index = m_variables[i]->variable_index();
		max_index = index > max_index ? index : max_index;
	}

	m_variables_values.resize(max_index+1);
	for(i=0 ; i<n ; ++i)
	{
		index = m_variables[i]->variable_index();
		m_variables[i]->pointer_to_value(&(m_variables_values[index]));
	}
}

Parser::Parser(string expression) : m_expression(expression)
{
	init();
}

Parser::Parser(const Parser& p) : m_expression(p.m_expression)
{
	init();
}

Parser& Parser::operator = (const Parser& p)
{
	if(this == &p) return *this;
	
	clear();
	m_expression = p.m_expression;
	init();

	return *this;
}

bool Parser::have_one_sequence(const std::vector<hNode>& v, int l, int r) const
{
	if(l==r) return true;

	if(v[l]->to_string() == "(" && v[r]->to_string() == ")")
	{
		int k, cont = 1;
		for(k=l+1 ; k<=r ; ++k)
		{
			if(v[k]->to_string() == "(") ++cont;
			if(v[k]->to_string() == ")") --cont;
			if(cont == 0) break;
		}
		if(k == r && cont == 0)
			return true;
	}

	return false;
}


void Parser::tree(std::vector<hNode>& v, int l, int r, hNode& root)
{
	if(l==r){ 
		root = v[l]; 
		return; 
	}

	Parser::Function* f = dynamic_cast<Parser::Function*>(v[l]);
	if(f)
	{
		if(have_one_sequence(v,l+1,r)) // inicia e comeca com parenteses de uma mesma sequencia
		{
			root = v[l];
			tree(v,l+1,r,f->parameter());
			return;
		}
	}

	if(have_one_sequence(v,l,r)) // inicia e comeca com parenteses de uma mesma sequencia
	{
		delete v[l]; 
		delete v[r];
		tree(v,l+1,r-1,root);
		return;
	}

	int i, pi, min = -1, pmin = 1000000;
	for(i=l, min=i ; i<=r ; ++i)
	{
		if(v[i]->to_string() == "(")
		{
			while(v[i]->to_string() != ")") ++i;
			++i;
		}

		if(i>r) break;

		pi = v[i]->precedence();
		if(pmin >= pi)
		{
			min = i;
			pmin = pi;
		}
	}

	root = v[min];
	Parser::Operator* op = dynamic_cast<Parser::Operator*>(root);
	if(op)
	{
		tree(v,l,min-1,op->left());
		tree(v,min+1,r,op->right());
	}

}

void Parser::plot_tree() const
{
	m_root->print_tree(0);
}

Parser::hNode Parser::get_next(int& i, const string st, bool prev_is_number) const
{
	int n = st.size();
	while(st[i] == ' ' && i<n) ++i;

	if (i >= n) 
	{
		#ifdef _DEBUG
		cerr << "warning : end of expression.\n";
		#endif
		return 0;
	}

	if(st[i] == '-' && !prev_is_number)
	{
		++i;
		return new Parser::Function("-");
	}

	if(is_variable(&st[i])) return get_variable(i,st);
	if(is_operator(&st[i])) return get_operator(i,st);
	if(is_function(&st[i])) return get_function(i,st);
	if(is_number  (&st[i])) return get_number  (i,st);

	cerr << "warning : invalid element.\n";
	return 0;
}

bool Parser::is_operator(const char* c) const
{
	if (*c == '(') return true;
	if (*c == ')') return true;
	if (*c == '+') return true;
	if (*c == '-') return true;
	if (*c == '*') return true;
	if (*c == '/') return true;
	if (*c == '^') return true;
	return false;
}

bool Parser::is_function(const char* c) const
{
	if(*c >= 'a' && *c<= 'z') return true;
	if(*c >= 'A' && *c<= 'Z') return true;
	if(*c == '_') return true;

	return false;
}

bool Parser::is_number(const char* c) const
{
	if(*c >= '0' && *c <= '9') return true;
	if(*c == '.') return true;
	return false;	
}

bool Parser::is_variable(const char* c) const
{
	char ch = *c;
	ch |= ' '; 
	if(ch >= 'x' && ch <= 'z')
	{
		++c;
		if(ch == 'x') while( *c >= '0' && *c <= '9' ) ++c;
		if( (*c == ' ') || (*c == '\0') ) return true;
		if(is_operator(c)) return true;
	}

	return false;
}


Parser::hNode Parser::get_operator(int& i, const std::string& st) const
{
	string op;
	op += st[i++];
	
	Parser::hNode node = new Parser::Operator(op); 
	return node;
}

Parser::hNode Parser::get_function(int& i, const std::string& st) const
{
	string f;
	int n = st.size();
	for(;;)
	{
		f += st[i++];
		if(i==n) break;
		if(st[i] == ' ') break;
		if(st[i] == '(') break;
	}

	return new Parser::Function(f); 
}

Parser::hNode Parser::get_number(int& i, const std::string& st) const
{
	double num = 0;

	while(st[i] >= '0' && st[i] <= '9')
	{
		num *= 10;
		num += st[i++] - '0';
	}

	if(st[i] == '.') ++i;

	double div = 1;
	while(st[i] >= '0' && st[i] <= '9')
	{
		div *= 10;
		num += (st[i++] - '0')/div;
	}
		
	return new Parser::Number(num); 
}

Parser::hNode Parser::get_variable(int& i, const std::string& st) const
{
	std::string v;
	int n = st.size();
	while( i<n && st[i] != ' ' && !is_operator(&st[i]) ) v+=st[i++];

	return new Parser::Variable(v);
}

Parser::~Parser(void)
{
	clear();
}

void Parser::clear()
{
	if(m_root)
		delete m_root;
	m_variables.clear();
	m_variables_values.clear();
	m_expression.clear();
}

double Parser::operator()(vector<double> param) 
{
	int n = param.size();
	int m = m_variables_values.size();

	int i;
	for(i=0 ; i<n && i<m ; ++i)
		m_variables_values[i] = param[i];

	for(i=n ; i<m ; ++i)
		m_variables_values[i] = 0;

	return m_root->evaluate();
}

std::string Parser::to_string() const
{
	return m_root->to_string_exp();
}

//=================================================================
// Function
//=================================================================

double Parser::Function::evaluate() const
{
	double v = m_parameter->evaluate();
	
	if(m_function == "-"  ) return -v;
	if(m_function == "sin") return sin(v);
	if(m_function == "cos") return cos(v);
	if(m_function == "tan") return tan(v);
	if(m_function == "abs") return abs(v);
	if(m_function == "exp") return exp(v);
	if(m_function == "log") return log(v);
	if(m_function == "log10") return log10(v);

	cerr << "warning : invalid operator " << m_function << endl;
	return 0;
}

void Parser::Function::print_tree(int h) const 
{  
	for(int i=0; i<h ; ++i) cout << '\t';
	print(cout);
	cout << '\n';
	m_parameter->print_tree(h+1);
}

Parser::Function::Function(std::string function, Parser::hNode parameter)
: m_function(function), m_parameter(parameter) 
{}

Parser::Function::~Function() 
{ 
	if(m_parameter) 
		delete m_parameter; 
}

Parser::hNode& Parser::Function::parameter()
{ 
	return m_parameter; 
}

void Parser::Function::print(std::ostream& os) const 
{ 
	os << m_function ; 
}

int Parser::Function::precedence() const 
{ 
	return 1000; 
}

std::string Parser::Function::to_string() const 
{ 
	return m_function; 
}

std::string Parser::Function::to_string_exp() const 
{ 
	if(m_function == "-" && m_parameter->h() == 1)
		return m_function + m_parameter->to_string_exp();

	return m_function + "(" + m_parameter->to_string_exp() + ")"; 
}

int Parser::Function::h() const
{
	int h = 1;
	if(m_parameter) h+= m_parameter->h();
	return h;
}

int Parser::Function::lower_precedence() const
{
	int p1 = precedence();
	int p2 = p1;
	if(m_parameter) p2 = m_parameter->lower_precedence();
	return (p1 < p2) ? p1 : p2;
}

//=================================================================
// Operator
//=================================================================

double Parser::Operator::evaluate() const
{
	double a = m_left->evaluate();
	double b = m_right->evaluate();

	if(m_operator == "+") return a + b;
	if(m_operator == "-") return a - b;
	if(m_operator == "*") return a * b;
	if(m_operator == "/")
	{
		if(b == 0)
		{
			cerr << "warning : division by 0." << endl;
		}
		return a / b;
	}
	if(m_operator == "^") return pow(a,b);

	cerr << "warning : invalid operator " << m_operator << endl;
	return 0;
}

int Parser::Operator::precedence() const
{
	if(m_operator == "(") return 10000;
	if(m_operator == ")") return 10000;
	if(m_operator == "+") return 1;
	if(m_operator == "-") return 1;
	if(m_operator == "*") return 2;
	if(m_operator == "/") return 2;
	if(m_operator == "^") return 3;

	return -1;
}

void Parser::Operator::print_tree(int h) const
{
	m_right->print_tree(h+1);
	for(int i=0; i<h ; ++i) cout << '\t';
	print(cout);
	cout << '\n';
	m_left->print_tree(h+1);
}

Parser::Operator::Operator(const std::string& op, Parser::hNode left, Parser::hNode right)
: m_left(left), m_right(right), m_operator(op) 
{}

Parser::Operator::~Operator() 
{ 
	if(m_left) 
		delete m_left; 
	if(m_right) 
		delete m_right; 
}

Parser::hNode& Parser::Operator::left() 
{ 
	return m_left; 
}

Parser::hNode& Parser::Operator::right() 
{ 
	return m_right; 
}

void Parser::Operator::print(std::ostream& os) const 
{ 
	os << m_operator; 
}

std::string Parser::Operator::to_string() const 
{ 
	return m_operator; 
}

std::string Parser::Operator::to_string_exp() const 
{ 
	std::string a = m_left->to_string_exp();
	std::string b = m_right->to_string_exp();

	if( m_left ->h() > 1 && m_left->lower_precedence() < precedence()  )   a = "(" + a + ")";
	if( m_right->h() > 1 && m_right->lower_precedence() < precedence() )  b = "(" + b + ")";

	return a + m_operator + b; 
}


int Parser::Operator::h() const
{
	int h = 1, hl = 0, hr = 0; 
	if(m_left)  hl = m_left->h();
	if(m_right) hr = m_right->h();
	return h += hl > hr ? hl : hr;
}

int Parser::Operator::lower_precedence() const
{
	int p1 = precedence();
	int p2 = p1, p3 = p1;
	if(m_left) p2 = m_left->lower_precedence();
	if(m_right) p3 = m_right->lower_precedence();
	p1 = (p1 < p2) ? p1 : p2;
	return (p1 < p3) ? p1 : p3;
}

//=================================================================
// Number
//=================================================================

void Parser::Number::print_tree(int h) const
{
	for(int i=0; i<h ; ++i) cout << '\t';
	print(cout);
	cout << '\n';
}

Parser::Number::Number(double n) : m_value(n) 
{}

double Parser::Number::evaluate() const 
{ 
	return m_value; 
}

void Parser::Number::print(std::ostream& os) const 
{ 
	os << m_value; 
}

int Parser::Number::precedence() const 
{ 
	return 1000; 
}

std::string Parser::Number::to_string() const 
{ 
	std::stringstream st; st << m_value; return st.str(); 
}

std::string Parser::Number::to_string_exp() const 
{ 
	std::stringstream st;
	st << m_value;
	return st.str();
}

int Parser::Number::h() const
{
	return 1;
}

int Parser::Number::lower_precedence() const
{
	return precedence();
}


//=================================================================
// Variable
//=================================================================

void Parser::Variable::print_tree(int h) const
{
	for(int i=0; i<h ; ++i) cout << '\t';
	print(cout);
	cout << '\n';
}

Parser::Variable::Variable(std::string v, double* n) : m_variable(v), m_value(n) 
{
	if(v == "x") m_index = 0;
	if(v == "y") m_index = 1;
	if(v == "z") m_index = 2;

	if(v[0] == 'x')
	{
		m_index = 0;
		int i, n = v.size();
		for(i = 1 ; i<n ; ++i)
		{
			m_index *= 10;
			m_index += v[i] - '0';
		}
	}

	m_index=0;
}

double Parser::Variable::evaluate() const 
{ 
	return *m_value; 
}

void Parser::Variable::print(std::ostream& os) const 
{ 
	os << m_variable; 
}

int Parser::Variable::precedence() const 
{ 
	return 1000; 
}

std::string Parser::Variable::to_string() const 
{ 
	return m_variable; 
}

std::string Parser::Variable::to_string_exp() const 
{ 
	return m_variable;
}

int Parser::Variable::h() const
{
	return 1;
}

int Parser::Variable::lower_precedence() const
{
	return precedence();
}

int Parser::Variable::variable_index() const
{
	return m_index;
}

void Parser::Variable::pointer_to_value(double *v) 
{ 
	m_value = v; 
}

